//一般性压入与重标记
//generic_push_relabel.cpp

//我并不准备先讲完增广路径类算法再讲预留推进类算法
//读者在阅读完本节所有算法之后自然会明白我为什么不这么做
//
//一般性压入与重标记算法属于预留与推进类算法，用该算法求最大流问题

//1)基础概念
//节点的余流：
//把流网络中的节点看做可以存储无穷多水的水池
//进入节点u的总净流是u的余流(即u存储的水量，也可以流向其他节点)，记作excess(u)
//节点的余流是非负数，当节点u没有余流时
//即使它拥有出弧边(向外运输的边)也无法向它的邻节点输出流
//余流是预留与推进类算法的核心技术
//距离标号d：
//也称距离函数，算法导论中称之为高度函数h
//每个节点的距离 d 值是残留网络中该节点到汇点的距离(一条边算一个单位距离)
//距离标号d的本质是残留网络中各节点的拓扑排序，汇点的d值恒为0
//溢出：
//节点u拥有余流时，它是溢出的
//若节点u余流为0，即使它向外的边有残余容量，u也无法压出流
//容许边：
//设节点u的出弧边(向外发出的边)上的邻节点是v，即该边是从u到v的边
//若该边的残留容量大于0(具有运输能力)，且两节点的距离标号满足d[u] = d[v] + 1
//则称这条边是节点u的一条容许边(注意并非有运输能力的边就是容许边)
//使用距离标号的目的是优先考虑拓扑顺序上相邻的节点
//从而尽快的找出一条增广路径
//
//容许边的概念也是最大流算法中非常重要的概念
//
//压入：
//找出u节点的一条容许边，将u的余流(余流大于0)通过这条容许边压入到它的邻节点中
//当然要尽可能压入最多的流，这个值是u的余流和容许边的容量中较小的那个值
//压入操作的副作用就是“添加反向边”，这个副作用存在于最大流的所有算法中
//重标记：
//执行压入操作之后需要更新网络流，添加反向边
//添加反向边之后流网络的拓扑顺序会发生变化
//可以通过对流网络所有节点进行一次拓扑排序得到当前残留网络中各节点的拓扑顺序
//但该方法每次都会遍历流网络中所有节点，时间复杂度较高
//而重标记操作是一种效率很高的更新方法
//更新残留网络之后流网络中会存在这样的情况：
//节点u向它所有的容许边都进行了最大程度的压入操作之后仍然拥有余流excess(u)
//这是检查节点u的所有的出弧边(向外的边)
//找出这些边的邻节点中d值最小的那个，将u的d值变为这个最小值加1
//重标记u之后就可以把u的余流更多的压入给它的邻节点
//前置流：
//结合上面的概念，前置流就是流网络中将源点的流最大可能的先存储在它的邻节点中
//这些邻节点也可以将自己存储的流压入给各自的邻节点
//这样带有类似缓冲池，允许流先存储在节点上的流网络即为前置流
//
//2)具体实现
//定义余流数组excess，excess[i]指代节点i的余流，初始excess[beg]为INF，其他为0
//定义距离标号(距离函数)d，d[i]指代节点i的距离标号
//即当前残留网络中节点i到汇点的拓扑距离，汇点的距离标号恒为0
//
//一般性压入与重标记算法中，只有压入操作与重标记操作是确定的
//而对节点进行该操作的顺序没有确定的说明，或者说随机的顺序都可以

//int generic_push_relabel(graph_matrix residue, int beg, int end)
